#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=9820788
#Facebook interview question
"""
there is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on..
It looks something like this 
1
2 3
4 5 6
every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on.
Now given C and M .Find the amount of water in ith cup.
"""
from utils import *

def get_water_amount(capacities, M):
    capacities = [float(c) for c in capacities]
    n = len(capacities)
    level = 2
    amounts = [M]
    for i in range(2, n + 1):
        #first node
        if i == level * (level - 1) / 2 + 1:
            amount = max(0, amounts[i - level] - capacities[i - level]) / 2
        #last node
        elif i == level * (level + 1) / 2:
            amount = max(0, amounts[i - level - 1] - capacities[i - level - 1]) / 2
            level += 1
        else: #other nodes
            amount = max(0, amounts[i - level] - capacities[i - level]) / 2 + max(0, amounts[i - level - 1] - capacities[i - level - 1]) / 2
        amounts.append(amount)
    for i in range(0, n):
        amounts[i] = min(amounts[i], capacities[i])
    return amounts

if __name__ == '__main__':
    capacities = random_arr(15, 10, 30)
    amounts = get_water_amount(capacities, 100)
    print capacities, 100
    print amounts


